Content addressable memory (CAM) devices, sometimes also referred to as “associative memories”, can provide rapid matching functions between an applied data value (e.g., a comparand, compare data, or search key) and stored data values (e.g., entries). Such rapid matching functions are often utilized in routers, network switches, and the like, to process network packets. As but two examples, a CAM can be utilized to search access control lists (ACLs) or forwarding information bases (FIBs). As is well know, an ACL can include a set of rules (data set) that can limit access (e.g., forwarding of packets) to only those packets having fields falling within a particular range. A FIB can include data necessary for forwarding a packet, typically the generation of a “next hop” address in response to a destination address.
A typical CAM device can store a number of data values in a CAM cell array. In a compare (i.e., search) operation, entries can be compared to a compare data value. An entry that matches the compare data value can result in the generation of a HIT indication. In addition, a typical CAM device can also include prioritization of HIT results. That is, if multiple entries match a given compare data value (multiple match case), one entry can be selected as a “winning” entry according to predetermined criteria. In many cases, an entry having the lowest address is selected as the winning entry in a multiple match case.
Conventionally, a CAM device may be divided into multiple CAM blocks, each of which can include its own prioritization circuitry. Such a division can be advantageous in power management and table management of the device.
Basic CAM device operations can include simple lookup operations, followed by single entry writes and/or reads. However, more sophisticated applications can involve more complex operations. For example, in more complex table management schemes, it may be desirable to invalidate (i.e., block) all entries beyond a particular physical address.
One example of a CAM device is shown in U.S. Pat. No. 6,240,000 issued to Sywyk et al. on May 29, 2001. This patent shows how a comparand value can be sequentially compared to different CAM blocks within different portions of a single clock cycle to reduce peak transient currents. Sywyk et al. also shows embodiments that receive portions of a comparand as input values, and combine search results from such portion to give an overall match result for a comparand larger than a received input value.
Commonly owned co-pending U.S. patent application Ser. No. 10/746,899 titled STAGGERED COMPARE ARCHITECTURE FOR CONTENT ADDRESSABLE MEMORY (CAM) DEVICE by Om et al. now U.S. Pat. No. 6,958,925 B1, issued on Oct. 25, 2005, discloses a CAM device that can split a compare data value into multiple portions for comparison on subsequent clock cycles. The contents of this patent application are incorporated by reference herein.
To better understand various features of the disclosed embodiments, other conventional approached to accommodating table update functions will now be described.
A first conventional approach to invalidating entries beyond a certain range is set forth in FIG. 8. FIG. 8 shows a conventional CAM device 800 having an array 802 with 1024 CAM entries having physical addresses from 0 to 1023. Data can be written to such entries via an interface 806. Each entry includes bit locations for storing a data value DATA. In addition, each entry also includes a bit location for storing a valid bit V. If a valid bit is set in an entry (in this example is a “1”), the entry can generate a match (hit) indication if the corresponding search key value matches the stored data value DATA. However, if a valid bit is not set (in this example is a “0”), the entry generates a mismatch (MISS) regardless of a given search key value.
FIG. 8 illustrates an operation that seeks to block those entries having a physical address greater than “557”. In the example shown, a sequence of write operations 804 can be executed, to clear the valid bits of entries at addresses 558 to 1023.
While such an approach can accomplish the given task, the large number of write operations needed can be time consuming and cumbersome to execute. Additionally, in some implementations, such operations can overwrite existing data, thus preventing such data values from being used at a later point in time. Still further, in order to “unblock” the entries, the same number of writes will be needed to set a valid bit in each entry.
A second conventional approach to block entries within a certain range is set forth in FIG. 9. FIG. 9 shows a system 900 having a CAM device 902 and an application specific integrated circuit (ASIC) 904 designed to execute predetermined search and related operations. A CAM device 902 can include a number of different CAM blocks 906-0 to 906-N, each of which can be selectively disabled by a command from ASIC 904.
In the system of FIG. 9, certain ranges of entries can be excluded with an iterative process. As shown in the figure, a search command can be received by CAM device 902 (1), resulting in the generation of a search result (2) from CAM block 906-N. In response to such a search result, ASIC 904 can write a command back into CAM device 902 that disables CAM block 906-N.
A drawback to the arrangement of FIG. 9 can be response time, complexity of the resulting system, and lack of “granularity” in entry organization. In particular, commands must make a loop from the CAM device 902 to the ASIC 904, and then from the ASIC 904 back to the CAM device 902. This can increase response time. Added complexity arises from the programming/design needed in the ASIC 904 to execute the indicated commands. Finally, a CAM device 902 can be disabled only a block at a time. Thus, when tables are blocked with the above method, only one table may be stored in any given CAM block (906-0 to 906-N).
In light of the above, it would be desirable to arrive at some way of enabling suppression of hit indications in CAM device that is more flexible and/or faster than the above conventional approaches.